# coding=utf-8
"""
Question:
有三个水桶，分别为8L，5L，3L，
现在有8L的水在8L的桶里，怎样倒水可以平分成两份；
桶没有刻度，不可以借助其他工具。
"""

# 水桶的状态模型(8L,5L,3L)中的水量
# initstate： (8, 0, 0)
# finalstate ： (4, 4, 0)
# 记录已经处理过的状态,防止死循环
# 状态迁移的动作记录数据结构使用map和list的复合结构,来表示树形结构


# 动作模型
'''
   倒水的动作:从哪到哪倒多少;
    给水桶编号ABC,即方向为三个水桶的全排列,倒水量视情况而定（临时计算）
'''


class Action:
    def __init__(self, fromwhere: str, towhere: str, water):
        self.fromwhere = fromwhere
        self.towhere = towhere
        self.water = water


# 动态计算倒水量
def computeaction(act: Action, fromstate):
    if act.fromwhere == 'big' and act.towhere == 'mid':
        act.water = min(fromstate[0], 5 - fromstate[1])
    elif act.fromwhere == 'big' and act.towhere == 'small':
        act.water = min(fromstate[0], 3 - fromstate[2])
    elif act.fromwhere == 'mid' and act.towhere == 'big':
        act.water = min(fromstate[1], 8 - fromstate[0])
    elif act.fromwhere == 'mid' and act.towhere == 'small':
        act.water = min(fromstate[1], 3 - fromstate[2])
    elif act.fromwhere == 'small' and act.towhere == 'big':
        act.water = min(fromstate[2], 8 - fromstate[0])
    else:
        act.water = min(fromstate[2], 5 - fromstate[1])
    return act


# 实行倒水动作
def doaction(fromstate: tuple, act: Action):
    if act.water == 0:
        return fromstate
    if act.fromwhere == 'big' and act.towhere == 'mid':
        return fromstate[0] - act.water, fromstate[1] + act.water, fromstate[2]
    elif act.fromwhere == 'big' and act.towhere == 'small':
        return fromstate[0] - act.water, fromstate[1], fromstate[2] + act.water
    elif act.fromwhere == 'mid' and act.towhere == 'big':
        return fromstate[0] + act.water, fromstate[1] - act.water, fromstate[2]
    elif act.fromwhere == 'mid' and act.towhere == 'small':
        return fromstate[0], fromstate[1] - act.water, fromstate[2] + act.water
    elif act.fromwhere == 'small' and act.towhere == 'big':
        return fromstate[0] + act.water, fromstate[1], fromstate[2] - act.water
    else:
        return fromstate[0], fromstate[1] + act.water, fromstate[2] - act.water


actions = [Action('big', 'mid', None),
           Action('big', 'small', None),
           Action('mid', 'big', None),
           Action('mid', 'small', None),
           Action('small', 'mid', None),
           Action('small', 'big', None)]


def moveitwithhistory(fromstate: tuple, history=None):
    """
    倒水过程中，显示状态历史
    """
    if history is None:
        history = []
    if fromstate in history:
        return
    tmpstate = fromstate
    history.append(fromstate)
    tmphistory = history.copy()
    # print('history:%s' % history)
    if fromstate == (4, 4, 0):
        # print('state %s is already visit' % str(fromstate))
        print('%s' % history)
        return
    for action in actions:
        action = computeaction(action, fromstate)
        if action.water == 0:
            continue
        # print('action = %s >> %s ,water=%d' % (action.fromwhere, action.towhere, action.water))
        nextstate = doaction(fromstate, action)
        moveitwithhistory(nextstate, history)
        fromstate = tmpstate
        history = tmphistory.copy()


if __name__ == '__main__':
    moveitwithhistory((8, 0, 0))
